public class MyLinkedList {

  private Node head;
  private Node last;
  private int size;

  public void insert(int index, int data) throws Exception {
      if (index<0 || index>size) {
          throw new IndexOutOfBoundsException("over link node range!");
      }
      Node insertedNode = new Node(data);
      if(size == 0){
          head = insertedNode;
          last = insertedNode;
      } else if(index == 0){
          insertedNode.next = head;
          head = insertedNode;
      }else if(size == index){
          last.next = insertedNode;
          last = insertedNode;
      }else {
          Node prevNode = get(index-1);
          insertedNode.next = prevNode.next;
          prevNode.next = insertedNode;
      }
      size++;
  }

  public Node remove(int index) throws Exception {
      if (index<0 || index>=size) {
          throw new IndexOutOfBoundsException("over link node range");
      }
      Node removedNode = null;
      if(index == 0){
          removedNode = head;
          head = head.next;
      }else if(index == size-1){
          Node prevNode = get(index-1);
          removedNode = prevNode.next;
          prevNode.next = null;
          last = prevNode;
      }else {
          Node prevNode = get(index-1);
          Node nextNode = prevNode.next.next;
          removedNode = prevNode.next;
          prevNode.next = nextNode;
      }
      size--;
      return removedNode;
  }

  public Node get(int index) throws Exception {
      if (index<0 || index>=size) {
          throw new IndexOutOfBoundsException("over link node range!");
      }
      Node temp = head;
      for(int i=0; i<index; i++){
          temp = temp.next;
      }
      return temp;
  }

  public void output(){
      Node temp = head;
      while (temp!=null) {
          System.out.println(temp.data);
          temp = temp.next;
      }
  }

  private static class Node {
      int data;
      Node next;

      Node(int data) {
          this.data = data;
      }
  }

  public static void main(String[] args) throws Exception {
      MyLinkedList myLinkedList = new MyLinkedList();
      myLinkedList.insert(0,3);
      myLinkedList.insert(0,4);
      myLinkedList.insert(2,9);
      myLinkedList.insert(3,5);
      myLinkedList.insert(1,6);
      myLinkedList.remove(0);
      myLinkedList.output();
  }
}
